﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SAI
{
    class TilePuzzleNode : Node
    {
        static int IDNum = 0;
        public static Dictionary<string, TilePuzzleNode> AllStates = new Dictionary<string, TilePuzzleNode>();
        PuzzleState _state;
        public List<Node> OutNeighbors { get { return calcNeighbors(); } }

        public TilePuzzleNode(PuzzleState state) : base("1")
        {
            _state = state;
        }

        private List<Node> calcNeighbors()
        {
            
            if (_outNeighbors.Count > 0)
                return _outNeighbors;
            List<Node> neighbors = new List<Node>();
            // create all neighbors
            int[] ind = _state.ZeroInd;
            int row = ind[0], col = ind[1];
            int dimension = _state.Dimension;
            // move left
            if (col < dimension - 1)
            {
                int[][] newState = copyState(_state.State);
                newState[row][col] = newState[row][col + 1];
                newState[row][col + 1] = 0;
                TilePuzzleNode tmp;
                if (!AllStates.TryGetValue(arrToString(newState),out tmp))
                {
                    tmp = new TilePuzzleNode(new PuzzleState(newState));
                    AllStates.Add(arrToString(newState), tmp);
                }
                neighbors.Add(tmp);
            }
            // move up
            if (row < dimension - 1)
            {
                int[][] newState = copyState(_state.State);
                newState[row][col] = newState[row + 1][col];
                newState[row + 1][col] = 0;
                TilePuzzleNode tmp;
                if (!AllStates.TryGetValue(arrToString(newState), out tmp))
                {
                    tmp = new TilePuzzleNode(new PuzzleState(newState));
                    AllStates.Add(arrToString(newState), tmp);
                }
                neighbors.Add(tmp);
            }

            // move right
            if (col > 0)
            {
                int[][] newState = copyState(_state.State);
                newState[row][col] = newState[row][col - 1];
                newState[row][col - 1] = 0;
                TilePuzzleNode tmp;
                if (!AllStates.TryGetValue(arrToString(newState), out tmp))
                {
                    tmp = new TilePuzzleNode(new PuzzleState(newState));
                    AllStates.Add(arrToString(newState), tmp);
                }
                neighbors.Add(tmp);
            }
           
            // move left
            if (row > 0)
            {
                int[][] newState = copyState(_state.State);
                newState[row][col] = newState[row - 1][col];
                newState[row - 1][col] = 0;
                TilePuzzleNode tmp;
                if (!AllStates.TryGetValue(arrToString(newState), out tmp))
                {
                    tmp = new TilePuzzleNode(new PuzzleState(newState));
                    AllStates.Add(arrToString(newState), tmp);
                }
                neighbors.Add(tmp);
            }
            _outNeighbors = neighbors;

            return neighbors;
        }

        public static string arrToString(int[][] arr)
        {
            string str = "";
            for (int i = 0; i < arr.Length; i++)
                for (int j = 0; j < arr[i].Length; j++)
                    str += arr[i][j] + " ";
            return str;
        }

        private int[][] copyState(int[][] arr)
        {
            int dimension = arr.Length;
            int[][] copy = new int[dimension][];
            for (int i = 0; i < dimension; i++)
            {
                copy[i] = new int[dimension];
                for (int j = 0; j < dimension; j++)
                    copy[i][j] = arr[i][j];
            }
            return copy;
            
        }
        public override void printNode()
        {
            _state.printState();
        }
        public override List<Node> getOutNeighbors()
        {
            return calcNeighbors();
        }


        internal void printPath()
        {
            if (this.Parent == null)
            {
                printNode();
                return;
            }

            TilePuzzleNode p = (TilePuzzleNode)(Parent);
            p.printPath();
            printNode();
                
            
        }
    }
}
